/**
 * 给定两个长度相同的数组，选择其中一个子段进行交换（也可以不换）
 * 交换后分别对两个数组求和，再取较大者，要求尽可能大，问最大可能是多少
 * 
 * 考虑交换过后数组1的和，组成部分为：
 * 没有交换的部分 + 2换过来的部分 = 数组1原有和 + (2换过来的部分 - 1换走的部分)
 * 
 * 注意到数组1原有和是一个固定值，因此就是要求后者的最大
 * 令 差数组 = 数组2 - 数组1
 * 就是求差数组的最大子段和
 * 
 * 再求一遍 数组1 - 数组2即可
 */
class Solution {

using vi = vector<int>;


public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        N = nums1.size();
        A.clear(); A.reserve(N);
        B.clear(); B.reserve(N);
        for(int i=0;i<N;++i){
            A.emplace_back(nums1[i] - nums2[i]);
            B.emplace_back(nums2[i] - nums1[i]);
        }

        auto t1 = maxSubArray(A);
        auto t2 = maxSubArray(B);

        auto s1 = accumulate(nums1.begin(), nums1.end(), 0);
        auto s2 = accumulate(nums2.begin(), nums2.end(), 0);

        return max(s1 + t2, s2 + t1);
    }

int N;
vi D;
vi U;
vi A, B;

public:
    int maxSubArray(vector<int>& nums) {
        N = nums.size();
        D.assign(N, 0);
        U.assign(N, 0);
        D[0] = U[0] = nums[0];
        for(int i=1;i<N;++i){
            U[i] = max(U[i - 1] + nums[i], nums[i]);
            D[i] = max(D[i - 1], U[i]);
        }
        return D[N - 1];
    }

};
